﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<unordered_map>
using namespace std;


//1171. 从链表中删去总和值为零的连续节点
//https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
// 给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

//删除完毕后，请你返回最终结果链表的头节点。




struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

//法1，前缀和+哈希表，遍历链表计算前缀和，当出现相同的前缀和时删除区间
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head)
    {
        ListNode* phead = new ListNode; //模拟头结点，解决从头开始删除的问题
        phead->next = head;
        unordered_map<int, ListNode*> hash_sum;
        ListNode* cur = phead->next;
        hash_sum[0] = phead;
        int sum = 0;
        while (cur)
        {
            sum += cur->val;
            if (hash_sum.count(sum) != 0) //前缀和重复
            {
                //1.删除哈希表中此区间的前缀和
                //2.删除链表中结点
                ListNode* prev = hash_sum[sum];
                ListNode* begin = prev;
                while (begin != cur)
                {
                    sum += begin->next->val;
                    hash_sum.erase(sum);
                    begin = begin->next;
                }
                hash_sum[sum] = prev; //前缀和写入哈希表

                prev->next = cur->next;//删除链表结点

            }
            else
            {
                hash_sum[sum] = cur;
            }
            cur = cur->next;
        }
        return phead->next;
    }
};



//法2，两次遍历，一次遍历写入前缀和，哈希表中的前缀和有两种情况： 1.被覆盖过，为最后一个  2.为第一次出现的
// 
//然后再次遍历链表计算并删除相同前缀和的区间。对应上面两种情况---》第二次遍历一定是第一次出现的，哈希表中一定是最后一次出现的，
//二者前缀和相同的话区间一定总和为0或者为空区间
int main()
{
    class Solution s1;
    struct ListNode p1;
    p1.val = 1;
    struct ListNode p2;
    p2.val = 2;
    struct ListNode p3;
    p3.val = -3;
    struct ListNode p4;
    p4.val = 3;
    struct ListNode p5;
    p5.val = 1;
    p1.next = &p2;
    p2.next = &p3;
    p3.next = &p4;
    p4.next = &p5;
    p5.next = NULL;
    s1.removeZeroSumSublists(&p1);
    return 0;
}
